// Simulate an interpreted  machine

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>

using namespace std;

int result, pc;
bool stop;

int reg[10], ram[1000], lram, ntest;

int main()
{
	scanf("%d\n", &ntest);
	for (int i = 0; i < ntest; i++)
	{
		memset(reg, 0, sizeof(reg));
		memset(ram, 0, sizeof(ram));
	
		string s;
		lram = 0;
		while (!cin.eof())
		{
			getline(cin, s);

			if (s == "") break;
			ram[lram++] = (s[0]-'0')*100 + (s[1]-'0')*10 + s[2]-'0';
		}

		pc = 0;
		result = 0;
		stop = false;
		int d[3];
	
		while (pc < lram)
		{
			d[0] = ram[pc] / 100;
			d[1] = (ram[pc] / 10) % 10;
			d[2] = ram[pc] % 10;
			pc++;

//			cout << "PC = " << pc << " ";
//			for (int j = 0; j < 3; j++) cout << d[j] << " " ;
//			cout << ":";
//			for (int j = 0; j < 10; j++) cout << reg[j] << " ";
//			cout << endl;

			switch (d[0])
			{
				case 1: 
					stop = true; break;
				case 2:
					reg[d[1]] = d[2]; break;
				case 3:
					reg[d[1]] = (reg[d[1]] + d[2]) % 1000; break;
				case 4: 
					reg[d[1]] = (reg[d[1]] * d[2]) % 1000; break;
				case 5:
					reg[d[1]] = reg[d[2]]; break;
				case 6:
					reg[d[1]] = (reg[d[1]] + reg[d[2]]) % 1000; break;
				case 7: 
					reg[d[1]] = (reg[d[1]] * reg[d[2]]) % 1000; break;
				case 8: 
					reg[d[1]] = ram[reg[d[2]]]; 
//					printf("ram[%d] --> %d\n", reg[d[2]], reg[d[1]]);
					break;
				case 9:
					ram[reg[d[2]]] = reg[d[1]]; 
//					printf("ram[%d] <-- %d\n", reg[d[2]], reg[d[1]]);
					break;
				case 0:	
					if (reg[d[2]] != 0) pc = reg[d[1]]; break;
			}
			result++;

			if (stop) {
				cout << result << endl;
				if (i < ntest-1) cout << endl;
				break;
			}
		}

	}
	return 0;
}
